package demo8;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 01背包问题 使用滚动数组进行空间上的优化
 */
public class test2 {
    public static void main(String[] args) {
        // 创建dp表
        int N = 1010;
        int n = 0,V = 0;
        int[] v = new int[N];
        int[] w = new int[N];
        int[] dp = new int[N];

        // 输入数据
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        V = sc.nextInt();
        for(int i = 1;i<=n;i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        // 第一问：不一定装满
        // 初始化 这里无需初始化
        for(int i = 1;i<=n;i++){
            for(int j = V;j >= v[i];j--){ // 修改遍历顺序
                dp[j] = Math.max(dp[j], dp[j-v[i]]+w[i]);
            }
        }
        System.out.println(dp[V]);

        // 重置dp表
        Arrays.fill(dp,0);

        // 第二问：必须装满
        // 初始化
        for(int j =1;j<=V;j++){
            dp[j] = -1;
        }
        for(int i = 1;i<=n;i++){
            for(int j = V;j >= v[i];j--){ // 修改遍历顺序
                if(dp[j-v[i]]!=-1){
                    dp[j] = Math.max(dp[j], dp[j-v[i]]+w[i]);
                }
            }
        }
        System.out.println(dp[V] == -1 ? 0 : dp[V]);
    }
}
